class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class ReCircularLinkedList {
    public static ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        if (head == null || head.next == null) {
            return null;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                ListNode i = head;

                //数学逻辑：（k + m + n）/ 2 = k + m  ->  m + k = n;因此再走（k + 1）步
                while (slow != i) {
                    i = i.next;
                    slow = slow.next;
                }

                return i;
            }
        }

        //必定非环，因为快慢指针未相遇
        return null;
    }

    // 主方法：用于测试
    public static void main(String[] args) {
        // 创建带环的链表: 1->2->3->4->2（环的入口是2）
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 形成环

        ListNode cycleEntry = detectCycle(node1);

        if (cycleEntry != null) {
            System.out.println("环的入口节点值是: " + cycleEntry.val);
        } else {
            System.out.println("链表中没有环");
        }
    }
}